/*:
 反转链表
 */

// [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)
// 1. 递归
func reverseList1(_ head: ListNode?) -> ListNode? {
    if head?.next == nil { return head }
    let newHead: ListNode? = reverseList1(head?.next)
    head?.next?.next = head
    head?.next = nil
    return newHead
}

// 2. 遍历
func reverseList2(_ head: ListNode?) -> ListNode? {
    var newHead: ListNode?, cur = head
    while cur != nil {
        let tmp = cur?.next
        cur?.next = newHead
        newHead = cur
        cur = tmp
    }
    return newHead
}

// 反转头n个节点
var successor: ListNode?
func reverseN(_ head: ListNode?, _ n: Int) -> ListNode? {
    if n == 1 {
        successor = head?.next
        return head
    }
    let newHead = reverseN(head?.next, n - 1)
    head?.next?.next = head
    head?.next = successor
    return newHead
}

// 反转链表2
func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
    var successor: ListNode?
    func reverseN(_ head: ListNode?, _ n: Int) -> ListNode? {
        if n == 1 {
            successor = head?.next
            return head
        }
        let newHead = reverseN(head?.next, n - 1)
        head?.next?.next = head
        head?.next = successor
        return newHead
    }

    if left == 1 {
        return reverseN(head, right)
    }

    head?.next = reverseBetween(head?.next, left - 1, right - 1)
    return head
}

// k个一组反转链表
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    var successor: ListNode?
    func _reverseN(_ head: ListNode?, _ n: Int) -> ListNode? {
        if n == 1 {
            successor = head?.next
            return head
        }
        let newHead = reverseN(head?.next, n - 1)
        head?.next?.next = head
        head?.next = successor
        return newHead
    }
    func reverseN(_ head: ListNode?, _ n: Int) -> ListNode? {
        var m = n, p = head
        while m > 1 {
            p = p?.next
            m -= 1
        }
        if p == nil { return head }
        successor = nil
        return _reverseN(head, n)
    }
    let dymmyHead = ListNode(0)
    dymmyHead.next = head
    var p: ListNode? = dymmyHead
    var q = p?.next
    var temp: ListNode? = reverseN(q, k)
    while temp !== q {
        p?.next = temp
        p = q
        q = p?.next
        ListNode.printNode(dymmyHead)
        temp = reverseN(q, k)
    }
    return dymmyHead.next
}

// 旋转链表
func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
    var pre = head, n = 1
    while pre?.next != nil {
        pre = pre?.next
        n += 1
    }
    pre?.next = head

    var move = n - (k % n)
    while move > 0 {
        pre = pre?.next
        move -= 1
    }
    let newHead = pre?.next
    pre?.next = nil
    return newHead
}

var head = ListNode(1)
head.next = ListNode(2)
head.next?.next = ListNode(3)
// head.next?.next?.next = ListNode(4)
// head.next?.next?.next?.next = ListNode(5)
// head.next?.next?.next?.next?.next = ListNode(3)
// head.next?.next?.next?.next?.next?.next = ListNode(6)

ListNode.printNode(head)
// head = reverseList2(head)!
// head = reverseN(head, 5)!
// head = reverseBetween(head, 2, 3)!
// head = reverseKGroup(head, 3)!
head = rotateRight(head, 4)!
ListNode.printNode(head)
